public class 滑动窗口最大值 {
    public static int MAXN = 100001;
    public static int[] deque = new int[MAXN]; // 双端队列维护, 头是最大值
    public static int h,t; // 维护的两个指针
    public int[] maxSlidingWindow(int[] nums, int k) {
        h = t = 0; // 双指针初始化
        int n = nums.length; // 数组的长度
        // 开始的一个双端队列的一个初始化, 把 k - 1 个元素先放到队列里面
        for (int i = 0; i < k - 1; i++) {
            // 队列队尾元素是否更小, 小的话判断下一个是否更小, 不断地替代掉
            while (h < t && deque[t - 1] <= nums[i]) {
                t--;
            }
            // 找到位置直接放入
            deque[t++] = i;
        }
        int m = n - k + 1; // 滑动窗口的数量
        int[] ans = new int[m]; // 返回的数组
        int l = 0; // 左边界
        for (int r = k - 1; l < m; r++,l++) {
            // 拿到第一个值看一下能大于几个元素, 然后进行一个加入队列
            while (h < t && nums[deque[t - 1]] <= nums[r]) {
                t--;
            }
            deque[t++] = r;
            // 把队列第一个元素的下标取出, 放入 ans
            ans[l] = nums[deque[h]];
            // 如果是第一个元素就 h++
            if (deque[h] == l) {
                h++;
            }
        }
        return ans;
    }
}
